﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

public class Solution53
{
    public int MaxSubArray2(int[] nums)//这个是递归法
    {
        int sum = 0;
        int max = int.MinValue;

        for (int i = 0; i < nums.Length; i++)
        {
            sum=Math.Max(sum+nums[i], nums[i]);
            max=Math.Max(max, sum);

        }
        return max;
    }
    //写一个贪心法
    public int MaxSubArray(int[] nums)//这个是递归法
    {
        int sum = 0;
        int max = int.MinValue;

        for (int i = 0; i < nums.Length; i++)
        {
            sum += nums[i];
            if(sum > max) max = sum;
            if(sum<0) sum = 0;//负数重新计算



        }
        return max;
    }
}

class program53
{

    static void Main53(string[] args)
    {

        Solution53 solution = new Solution53();

        int[] nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4];
      int res=  solution.MaxSubArray(nums);
        Console.WriteLine(res);
    }
}
